<head>
    <meta charset="UTF-8">
<title>算法训练 Candy Store</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>经营一家糖果店是非常困难的，你需要优化各种各样的东西。最近你在销售一种非常时髦的糖果，叫做Whizboppers。这种糖果变质非常迅速，所以：</div>
<div>&middot;你必须每天早上从供应商买来新的Whizboppers。</div>
<div>&middot;你必须用当天早上从供应商买来的盒子装着糖果出售。</div>
<div>&nbsp;</div>
<div>你可以从你的供应商处买来装有任意整数克糖果的盒子。&nbsp;</div>
<div>每天有至多k位顾客到你的店里来。从第1个人开始，每个人会选择花费整数分的钱来买Whizboppers，钱数在1分到C分之间（包含1分和C分）。你打算以1分钱每克的价格出售；所以如果一个人想要花4分钱，你会给他恰好4克糖果。你可以给他1个4克的盒子，也可能是1个2克的盒子和2个1克的盒子。&nbsp;</div>
<div>你最少需要买几个盒子才能保证，不管每个人想花多少钱买糖，你总是可以给他们对应质量的糖果？</div>
<div>&nbsp;</div>
<div>注意：当一个人选择自己想买多少糖果后，你知道之前的人已经买了多少糖，但不能预知之后的人打算买多少糖。&nbsp;</div>
<div style="text-align: left;">举个例子，如果每天至多有2位顾客到你的店里，每个人至多花2分钱(k=2,C=2)，你可以从你的供应商买4个1克的盒子。但是你可以做的更好：只要买2个1克的盒子和1个2克的盒子，就可以满足你的顾客。如下所示：</div>
<div style="text-align: center;">&nbsp;</div>
<table border="1">
    <tbody>
        <tr>
            <td style="text-align: center;">第一个人</td>
            <td style="text-align: center;">给第一个人的盒子&nbsp;</td>
            <td style="text-align: center;">第二个人</td>
            <td style="text-align: center;">给第二个人的盒子</td>
        </tr>
        <tr>
            <td style="text-align: center;">2分</td>
            <td style="text-align: center;">1 个 2克</td>
            <td>
            <p style="text-align: center;">2分</p>
            <p style="text-align: center;">1分</p>
            </td>
            <td>
            <p style="text-align: center;">2 个 1克</p>
            <p style="text-align: center;">1 个 1克</p>
            </td>
        </tr>
        <tr>
            <td style="text-align: center;">1分</td>
            <td style="text-align: center;">1 个 1克</td>
            <td>
            <p style="text-align: center;">2分</p>
            <p style="text-align: center;">1分</p>
            </td>
            <td>
            <p style="text-align: center;">1 个 2克</p>
            <p style="text-align: center;">1 个 1克</p>
            </td>
        </tr>
    </tbody>
</table>
<div style="text-align: center;">&nbsp;</div>
<div>不论第一个人怎么买，你都可以给他对应质量的盒子，同时保证第二个人也能拿到正确质量的糖果。所以对于k=2,C=2，你用3个盒子就可以满足任意的顾客需求。&nbsp;</div>
<p>【输入格式】</p>
<div>第一行一个整数T，表示询问数量。</div>
<div>接下来T行，每行包含两个整数k和C，分别表示最大人数和每个人花费的最多钱数。</div>
<p>【输出格式】<br />
对于每一个询问，输出一行包含&quot;Case #x: y&quot;，x是询问编号（从1开始标号），y是你每天最少需要的盒子数量。<br />
【样例输入】</p>
<div>4</div>
<div>1 5</div>
<div>2 2</div>
<div>10 3</div>
<div>2 50</div>
<p>【样例输出】</p>
<div>Case #1: 3</div>
<div>Case #2: 3</div>
<div>Case #3: 19</div>
<div>Case #4: 11</div>
<p>【数据规模和约定】<br />
对于25%的数据，k&lt;=20,C&lt;=3；<br />
对于另外20%的数据， k&lt;=1000,C&lt;=10；<br />
对于另外5%的数据，k=1；<br />
对于100%的数据，1 &lt;= T &lt;= 100，1 &lt;= k &lt;= 1000，1 &lt;= C &lt;= 10^12。</p>